Computer systems for graphics applications, such as computer aided drawing or computer animation, allow the generation of a drawing using one of several available input devices or peripherals. Input devices such as a digitizing tablet may be used to generate a drawing. Computer aided drawing systems may use a stylus motion to derive line direction, or trajectory information, and stylus pressure to derive line thickness. Generally, there are two types of graphics systems, one is image based and the other is vector based.
Image based systems store, manipulate and display a drawing as an array of picture elements. The display picture elements are called pixels, and a pixel array, typically stored in memory, is called a pixmap. The pixmap is used by the image display system to "paint" the corresponding pixels on the raster display device. An inherent limitation of an image based system is that the resulting digital image has a fixed, usually limited, spatial resolution, each pixel having a fixed size. Computer graphics systems may also be used to enlarge or shrink a portion of the drawing ( referred to as, respectively, zooming in or zooming out). In the case of image based systems, a "zoom" transformation is applied to the pixels of the pixmap to generate the corresponding pixels on the screen. When the scale factor of the transformation, i.e. the zoom factor, is less than 1, i.e. zooming out of the drawing, several pixmap pixels are mapped onto one screen pixel, resulting in a reasonable quality image. When the zoom factor of the transformation is greater than 1, i.e. zooming into the drawing, one pixmap pixel is mapped onto several screen pixels, resulting in a coarse, poor quality image. Current commercially available pixel displays have an upper limit on the order of 1024 pixels per line. For applications requiring smooth, high quality drawings, these image based systems are considered to have low resolution. For example, applications for high quality cartoon animation require higher resolution. With adequate high resolution, each drawing, called a cel, could then be reused and resized as necessary in the animation process.
Vector based systems store and manipulate a drawing as a series of vectors, i.e. lines defined by their starting and ending points, in a coordinate system where coordinates are known with good accuracy, typically numbers between -2147483648 and +2147483647 for a 32 bit system. A vector based system is an object oriented system in that the unit of description is a vector, not a pixel by pixel map. This kind of system can accommodate not just straight lines, but any shape line, as curves can be approximated for display or computation purposes to any desired accuracy by appropriate polylines, i.e. a series of vectors. Vectors more accurately represent the strokes forming the drawing because they can maintain the same accuracy under transformation. These vectors can then be displayed on conventional image based display system through a scan converter which produces the best possible image for a given transformation. Zooming in on a portion of the drawing by scaling the dimensions of the vectors in the vector based system does not distort the appearance of the displayed strokes, as would be inherently the case in an image based system. Vector based systems are thus considered to be resolution independent and, therefore, are used when "high" resolution is necessary. These systems are well suited to the animation production process, where it is important to have fine resolution, good quality cels. One of the steps of producing any finished drawing, particularly a cel in the computer aided cartoon animation process, is that of coloring the drawing. A closed region in the displayed drawing is selected by the user through an input device, such as a digitizing tablet or a mouse, and the system is activated to "fill" the selected region with a user selected color.
Image based systems use well known methods for coloring the drawing. One well known technique is referred to as the seed fill method. This method uses a seed pixel pointed to by the user as a starting point to change the pixel to the desired color. It then spreads the color to the neighboring pixels until the region boundaries are found. In image systems, a pixel belongs to the region boundary if its color, prior to modification, is different from the color, also prior to modification, of the seed pixel. When this method is applied on pixmap images of traditional size of 1024.times.1024, the number of pixels that need to be visited is limited to a maximum of 1048576 (when the area to color covers the entire display screen).
Vector based system are more difficult to handle, as the seed fill method becomes impractical, since it would have to be implemented on a very large pixmap of size 4294967295.times.4294967295. For vector based systems, it is necessary to know the vector description of the closed region which must be colored. Computing the description of the closed colorable region from an arbitrary series of vector strokes entered by an artist can be done with a method that derives the topology of a drawing from its geometry by computing the intersection of the vector strokes and processing the result. Such a method is described in the following article: Gangnet M., Herve' J-C., Pudet T., Van Thong J-M., "Incremental Computation of Planar Maps", SIGGRAPH '89 Proceedings, Addison-Wesley (1989). A planar map is a data structure generated from the geometric description of the various line paths, i.e. the strokes entered into the drawing by the user, which also further contains information describing intersection points (vertices), edges (the portion of a line path between two vertices), and regions (the sequence of edges describing a closed region). The article above describes how to derive the latter information from the former. A known vector based graphics system utilizing a planar map to iteratively insert and erase portions of a drawing, and color selected regions, is described in U.S patent application Ser. No. 07/513,247, filed on Apr. 20, 1990, and corresponding European Patent Document 0 395 482 A1.
However, one problem that still remains is that it is almost always necessary to edit the drawing, and the corresponding planar map, to avoid color leakage resulting from unintended and unwanted gaps between the user entered strokes. These unintended gaps are the result of hand drawn lines which might only appear to intersect other lines at the resolution used to display them, as the user draws them. As shown in FIG. 2A-B, this is the case particularly when the drawing strokes have been drawn with a variable width pen and the region boundaries have been computed and stored as the stroke center lines. In this case, the center lines might not intersect at their endpoints, though the stroke outlines might, making it difficult for the user to see exactly where the gaps may exist. These unintended gaps are usually found by the user when a seemingly closed area is painted and the paint spills over to an adjacent area through an unintended gap. This forces the user edit the drawing to eliminate these gaps. The user then must either overcompensate by retracing some of the strokes suspected to produce the non-intersecting lines, or searching for these gaps by zooming and panning the drawing. This correction process not only adds tedious and time consuming steps, but may also adversely affect the graphic quality of the drawing.